package com.cuz.daileetcode.bat100;

import java.util.HashMap;
import java.util.Objects;

public class 最长无重复字符字串 {
    public static void main(String[] args) {
        System.out.println(solution1("gabcadcef0"));
        System.out.println(solution2("gabcadcef0"));
        System.out.println(solution3("gabcadcef0"));
    }

    public static String solution1(String str) {
        if (str == null || str.length() <= 1) {
            return str;
        }
        int len = str.length();
        int[] dp = new int[len];
        String ans = null;
        char[] charArray = str.toCharArray();
        dp[0] = 1;
        HashMap<Character, Integer> charPreIndexMap = new HashMap<>();
        charPreIndexMap.put(charArray[0], 0);
        for (int index = 1; index < charArray.length; index++) {
            dp[index] = dp[index - 1] + 1;
            Integer preIndex = charPreIndexMap.get(charArray[index]);
            if (Objects.nonNull(preIndex)) {
                //k  a  b  c  a
                //0  1  2  3  4
                //index=4 preIndex=1 长度为index-preIndex=4-1=3
                dp[index] = Math.min(dp[index], index - preIndex);
            }
            charPreIndexMap.put(charArray[index], index);
            if (ans == null || ans.length() < dp[index]) {
                //k  a  b  c  a
                //0  1  2  3  4
                //dp[index]=dp[4]=3   4-3+1=2 ,4
                ans = str.substring(index - dp[index] + 1, index + 1);
            }
        }
        return ans;
    }

    public static String solution2(String str) {
        if (str == null || str.length() <= 1) {
            return str;
        }
        int maxLen = 1;
        String ans = null;
        char[] charArray = str.toCharArray();
        HashMap<Character, Integer> charPreIndexMap = new HashMap<>();
        charPreIndexMap.put(charArray[0], 0);
        for (int index = 1; index < charArray.length; index++) {
            maxLen += 1;
            Integer preIndex = charPreIndexMap.get(charArray[index]);
            if (Objects.nonNull(preIndex)) {
                //k  a  b  c  a
                //0  1  2  3  4
                //index=4 preIndex=1 长度为index-preIndex=4-1=3
                maxLen = Math.min(maxLen, index - preIndex);
            }
            charPreIndexMap.put(charArray[index], index);
            if (ans == null || ans.length() < maxLen) {
                //k  a  b  c  a
                //0  1  2  3  4
                //dp[index]=dp[4]=3   4-3+1=2 ,4
                ans = str.substring(index - maxLen + 1, index + 1);
            }
        }
        return ans;
    }

    public static String solution3(String str) {
        if (str == null || str.length() <= 1) {
            return str;
        }
        int left = 0;
        int right = 1;
        String ans = null;
        char[] charArray = str.toCharArray();
        HashMap<Character, Integer> charPreIndexMap = new HashMap<>();
        charPreIndexMap.put(charArray[0], 0);
        while (right < charArray.length) {
            Integer preIndex = charPreIndexMap.get(charArray[right]);
            if (preIndex != null) {
                left = preIndex + 1;
            }
            charPreIndexMap.put(charArray[right], right);
            //abc left=0 right=2
            if (ans == null || ans.length() < right - left + 1) {
                ans = str.substring(left, right + 1);
            }
            right++;
        }
        return ans;
    }
}
